home *** CD-ROM | disk | FTP | other *** search
/ Skunkware 5 / Skunkware 5.iso / src / X11 / wais / waisgate / trie.c < prev    next >
C/C++ Source or Header  |  1995-05-09  |  6KB  |  309 lines
  1. /* WIDE AREA INFORMATION SERVER SOFTWARE:
  2.    No guarantees or restrictions.  See the readme file for the full standard
  3.    disclaimer.
  4. */
  5.  
  6. #ifndef lint
  7. static char *RCSid = "$Header: /tmp_mnt/net/quake/proj/wais/wais-8-b5/ir/RCS/trie.c,v 1.2 92/02/12 13:52:49 jonathan Exp $";
  8. #endif
  9.  
  10. /* Change log:
  11.  * $Log:    trie.c,v $
  12.  * Revision 1.2  92/02/12  13:52:49  jonathan
  13.  * Added "$Log" so RCS will put the log message in the header
  14.  * 
  15.  * 
  16. */
  17.  
  18. /*
  19.   trie.c: This module provides an associative lookup table, based on
  20.   tries [see Knuth,D. Art of Computer Programming, Vol 3]
  21.  
  22.   Author: Simon E Spero (ses@ccgr.technion.ac.il)
  23.   This file is in the public domain.
  24.  
  25.   public functions:
  26.   
  27.   encode: encodes a string for searching
  28.  
  29.   make_trie_allocator: contructs a trie allocator
  30.   dispose_trie_allocator: dispose of a trie
  31.  
  32.   new_trie(string): 
  33.     creates a new trie containing only the entry `string'
  34.     
  35.   trie_lookup(word,dictionary,allocator).
  36.    This function looks up word in the dictionary, and, if found,
  37.    returns a pointer to it's datum. If the word is not found,
  38.    and allocator != NULL, the word will be added to the dictionary.
  39.    If an error occurs, the function returns NULL
  40. */
  41.   
  42.  
  43. #include <ctype.h>
  44. #include <stdio.h>
  45. #include "cutil.h"
  46. #include "trie.h"
  47.  
  48. /*
  49.  * Special purpose allocators for resources that are freed only in bulk
  50.  */
  51.  
  52. /*
  53.  * make a new allocator 
  54.  */
  55. allocator* make_allocator(item_size,free_func) 
  56. int item_size;
  57. void (*free_func)();
  58. {
  59.   allocator* tmp;
  60.   if (!(tmp = (allocator *)s_malloc(sizeof(allocator)))) {
  61.     return 0L;
  62.   }
  63.  
  64.   tmp->size=item_size;
  65.   tmp->dispose = free_func;
  66.   return tmp;
  67. }
  68.  
  69. /*
  70.  * dispose of an allocator
  71.  */
  72. void fast_free(alloc)
  73. allocator* alloc;
  74. {
  75.   
  76.   char *block;
  77.   int i,j;
  78.   int limit;
  79.   for(i=0;i<alloc->blocks_allocated;i++) {
  80.     if(alloc->dispose) {
  81.       block=alloc->tofree[i];
  82.       limit = (i+1 == alloc->blocks_allocated ? CHUNK_SIZE - alloc->items_left : CHUNK_SIZE);
  83.       for(j=0;j<limit;j++) {
  84.     alloc->dispose(block);
  85.     block += alloc->size;
  86.       }
  87.     }
  88.     free(alloc->tofree[i]);
  89.   }
  90. }
  91.  
  92. /*
  93.  * allocate an item
  94.  */
  95.  
  96. char* fast_alloc(alloc)
  97. allocator* alloc;
  98. {
  99.   
  100.   char* tmp;
  101.  
  102.   if (!alloc->items_left) {
  103.     if (alloc->blocks_allocated <MAX_BLOCKS &&
  104.     (tmp = (char *)s_malloc(alloc->size*CHUNK_SIZE))) {
  105.       alloc->tofree[alloc->blocks_allocated++] = tmp;
  106.       alloc->next_location = tmp +alloc->size;
  107.       alloc->items_left = CHUNK_SIZE-1;
  108.       return tmp;
  109.     } else {
  110.       return 0L;
  111.     }
  112.   } else {
  113.     tmp = alloc->next_location;
  114.     alloc->next_location += alloc->size;
  115.     alloc->items_left--;
  116.     return tmp;
  117.   }
  118. }
  119.  
  120. /*
  121.  * function to free non fast_alloced stuff from a trie.
  122.  *   should really be a lambda expression, but....
  123.  */
  124.  
  125. void  free_trie(dict)
  126. trie* dict;
  127. {
  128.   free(dict->string);
  129. }
  130.  
  131. /*
  132.  * make an allocator for tries
  133.  */
  134.  
  135. trie_allocator* make_trie_allocator()
  136. {
  137.   trie_allocator* tmp;
  138.   if(!(tmp = (trie_allocator*)s_malloc(sizeof(trie_allocator)))) {
  139.     return 0L;
  140.   }
  141.   if (!(tmp->tries = make_allocator(sizeof(trie),free_trie))) {
  142.     free(tmp);
  143.     return 0L;
  144.   }
  145.   if(!(tmp->trie_tables = make_allocator(sizeof(trie_table),0L))) {
  146.     free(tmp->tries);
  147.     free(tmp);
  148.     return 0L;
  149.   }
  150.   return tmp;
  151. }
  152.  
  153. /*
  154.  * dispose of a trie
  155.  */
  156.  
  157. void dispose_trie_allocator(alloc)
  158. trie_allocator* alloc;
  159. {
  160.   fast_free(alloc->tries);
  161.   fast_free(alloc->trie_tables);
  162.   free(alloc);
  163. }
  164.  
  165. /*
  166.  * make a trie with str as it's only entry
  167.  */
  168.  
  169. trie* new_trie(str,alloc)
  170. char* str;
  171. trie_allocator* alloc;
  172. {
  173.   trie* tmp;
  174.  
  175.   tmp=(trie*)fast_alloc(alloc->tries);
  176.   tmp->string=s_strdup(str);
  177.   tmp->table=0L;
  178.   tmp->datum=0L;
  179.   return tmp;
  180. }
  181.  
  182. trie ** new_trie_table(alloc)
  183. allocator* alloc; {
  184.  
  185.   trie** tmp;
  186.  
  187.   tmp=(trie **)fast_alloc(alloc);
  188.   if(!tmp) {
  189.     return 0L;
  190.   }
  191.   return tmp;
  192. }
  193.  
  194. /*
  195.   After all those allocators, finally a useful function! 
  196.   */
  197.  
  198. void **trie_lookup(key,dict,alloc)
  199.      char* key;
  200.      trie* dict;
  201.      trie_allocator* alloc;
  202. {
  203.  
  204.   char *c,*d;
  205.   trie *t,*t2;
  206.  
  207.   c = key;
  208.   d = dict->string;
  209.  
  210.   while(*c && *d && *c == *d) {
  211.     c++; d++;
  212.   }
  213.  
  214.   if (!*c ) { 
  215.     if(!*d) {
  216.       /* we found the answer*/
  217.       return &(dict->datum);
  218.     }
  219.     /* key was a prefix*/
  220.     if (!alloc) {
  221.       return 0L;
  222.     }
  223.     /* split this node */
  224.     t = new_trie(d+1,alloc);
  225.     t->table = dict->table;
  226.     t->datum = dict->datum;
  227.     dict->table= (trie **)new_trie_table(alloc->trie_tables);
  228.     dict->table[*d]=t;
  229.     dict->datum=0L;
  230.     dict->string=s_strdup(key);
  231.     return &(dict->datum);
  232.   }
  233.  
  234.   if(*d && *c != *d) { /* mismatch */
  235.     if (!alloc) {
  236.       return 0L;
  237.     }
  238.     t  = new_trie(d+1,alloc);
  239.     t2 = new_trie(c+1,alloc);
  240.     t->datum=dict->datum;
  241.     t->table=dict->table;
  242.     dict->table= (trie **)new_trie_table(alloc->trie_tables);
  243.     dict->table[*c] = t2;
  244.     dict->table[*d] = t;
  245.     dict->datum =0L;
  246.     *d='\0';
  247.     return &(t2->datum);
  248.   }
  249.   
  250.   /*
  251.     Follow the pointers in table, if there are any
  252.     */
  253.   if (!dict->table) {
  254.     if (!alloc) {
  255.       return 0L;
  256.     }
  257.     dict->table=(trie **)new_trie_table(alloc->trie_tables);
  258.   }
  259.   
  260.   if(dict->table[*c]) {
  261.     return trie_lookup(c+1,dict->table[*c],alloc);
  262.   } else {
  263.     if (!alloc) {
  264.       return 0L;
  265.     }
  266.     dict->table[*c] = new_trie(c+1,alloc);
  267.     return &(dict->table[*c]->datum);
  268.   }
  269.  
  270. }
  271.  
  272. /*
  273.   WARNING: IF CHECK_ALNUM IS UNDEFINED, MAKE SURE YOU PASS IN AN ALNUM,
  274.   OR ELSE
  275. */
  276.  
  277. int encode( s)
  278. unsigned char* s; {
  279.   register unsigned char * e;
  280.   unsigned char t;
  281.   for(e=s;*e;e++) {
  282. #ifdef CHECK_ALNUM
  283.     if (!isalnum(*e)) {
  284.       return 0;
  285.     }
  286. #endif
  287.     if (isdigit(*e)) {
  288.       *e = *e -'0' + 27;
  289.     } else {
  290.       *e = (*e & 31);
  291.     }
  292.   }
  293.   return 1;
  294. }
  295.  
  296.  
  297. void decode(s) 
  298. unsigned char* s;
  299. {
  300.   while(*s) {
  301.     if (*s < 27) {
  302.       *s += ('a'-1);
  303.     } else {
  304.       *s += ('0'-27);
  305.     }
  306.     *s++;
  307.   }
  308. }
  309.